#include "util.h"
#include "common_sort.h"

/*
插入排序递归算法
O(n)=O(n^2)

*/

void RecursiveInsertionSort::sort(std::vector<int>& vec, size_t sz) {
	// base case
	if (sz <= 1) {
		return;
	}

	// recursive sort first n-1 
	sort(vec, sz - 1);

	// insert last element at corrent posiont in sorted array
	int last = vec[sz - 1];
	int j = sz - 2;
	while (j >= 0 && vec[j] > last) {
		vec[j+1] = vec[j];
		--j;
	}

	vec[j+1] = last;
}
